package Other;

public class leet_121 {
    public static void main(String[] args) {
        Solution_121 p =new Solution_121();
        int[] nums = new int[]{7,1,5,3,6,4};
        int MaxProfits = p.maxProfit(nums);
        System.out.println(MaxProfits);
    }
}


class Solution_121 {
    public int maxProfit(int[] prices) {
        int MaxProfits = regressionPrice(prices);
        return MaxProfits;
    }

    /**
     * 动态回归算法解决问题
     * 此时dp为最小买入金额
     * @param prices
     * @return
     */
    public int regressionPrice(int[] prices){
        if(prices.length==0){
            return 0;
        }

        // 定义一个数组
        // 每个位置代表当前天数买入的最小值
        int[] dp=new int[prices.length];
        for(int i=0; i<prices.length; i++){
            if(i==0){
                dp[i] = prices[0];
            }else {
                int maxNum = Math.min(dp[i-1], prices[i]);
                dp[i] = maxNum;
            }
        }

        // 得到每天的买入最小的金额后
        int maxProfits = 0;
        for(int i=0; i<prices.length; i++){
            int tmpProfits = prices[i] - dp[i];
            if(maxProfits < tmpProfits){
                maxProfits = tmpProfits;
            }
        }
        return maxProfits;
    }




}